package com.jxb.four;

import com.jxb.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 路径总和 III
 * 10+5=15，10+5+3=18,10+5+3+3=21，10+5+3-2=16
 */
public class PathSumIII_437 {

    public static void main(String[] args) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(1,2);
        Integer orDefault = map.getOrDefault(2, 3);
        System.out.println(orDefault);
    }

    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer,Integer> prefixSum = new HashMap();
        prefixSum.put(0,1);
        //从根节点开始遍历
        return traversal(root,0,sum,prefixSum);
    }

    //root：当前的根节点
    //currSum：当前的总和
    //target：目标值
    //prefixSum：前缀和缓存记录
    //root：10，currSum：10，target：8，res：0，prefixSum：(10,1)
        //res = res + 5 + (-3)
    //root:5,currSum：15，target：8，res：7，prefixSum：(15,1)
    //root:3,currSum：15，target：8，res：7，prefixSum：(15,1)
    public int traversal1(TreeNode root, int currSum, int target,
                         HashMap<Integer, Integer> prefixSum) {
        if (root == null) {
            return 0;
        }
        currSum = currSum + root.val;
        Integer res = prefixSum.getOrDefault(currSum - target, 0);
        prefixSum.put(currSum,prefixSum.getOrDefault(currSum,0) + 1);
        res = res + traversal1(root.left,currSum,target,prefixSum)
                + traversal1(root.right,currSum,target,prefixSum);
        prefixSum.put(currSum,prefixSum.get(currSum) + 1);
        return res;
    }

    //root:2            1       5
    //currSum:17        18     15
    //res = 0           1       0
    //map:(17,1)
    public int traversal2(TreeNode root, int currSum, int target,
                          HashMap<Integer, Integer> prefixSum) {
        if (root == null) {
            return 0;
        }
        //计算前缀和
        currSum = currSum + root.val;
        //判断差值在字典表中是否有,没有的话，返回为0
        Integer res = prefixSum.getOrDefault(currSum - target, 0);
        //将当前的前缀和添加到字典表中
        prefixSum.put(currSum,prefixSum.getOrDefault(currSum,0) + 1);
        res = res + traversal2(root.left,currSum,target,prefixSum)
                + traversal2(root.right,currSum,target,prefixSum);
        prefixSum.put(currSum,prefixSum.get(currSum) + 1);
        return res;
    }

    public int traversal(TreeNode root, int currSum, int target,
                         HashMap<Integer, Integer> prefixSum) {
        if (root == null) {
            return 0;
        }
        currSum = currSum + root.val;
        //判断缓存中是否有前缀和，有，返回，没有返回0
        Integer res = prefixSum.getOrDefault(currSum - target, 0);
        prefixSum.put(currSum,prefixSum.getOrDefault(currSum,0)+1);
        //获取左子树+右子树+res
        res = res + traversal1(root.left,currSum,target,prefixSum)
                + traversal1(root.right,currSum,target,prefixSum);
        prefixSum.put(currSum,prefixSum.get(currSum) + 1);
        return res;
    }

    //记录次数
    int count = 0;

    // //暴力穷举
    // public int traversal(TreeNode root, int target) {
    //
    //     while (root != null) {
    //         int currSum = 0;
    //         calSum(root,target,currSum);
    //         root = root.left;
    //     }
    // }
    //
    // public int calSum(TreeNode root, int target,int currSum) {
    //     if (root == null) {
    //         return 0;
    //     }
    //     int left = root.left.val;
    //     int right = root.right.val;
    //     currSum += root.val;
    //     if ((currSum + left) == target) {
    //         currSum += left;
    //         count++;
    //     }
    //     if ((currSum + right) == target) {
    //         currSum += right;
    //         count++;
    //     }
    //     return calSum(root.left,target,currSum) + calSum(root.right,target,currSum);
    // }
}
